package org.example.Soution003;

public class JumpFromArray {
    public static void main(String[] args) {
        JumpFromArray obj = new JumpFromArray();
        int[] nums=new int[]{3,0,8,2,0,0,1};
        System.out.println(obj.canJump(nums));
        System.out.println(obj.jump(nums));

    }

    public boolean canJump(int[] nums) {
        int n = nums.length;
        if(n==1) return true;
        int flag=0;  //flag是下标
        while(flag<n) {
            int currentLength=nums[flag];  //记录当前最大值
            if(currentLength==0) break;
            if(flag+1+currentLength>=n) {
                return true;
            }
            int newFlag=flag+currentLength;  //找新最大路径的下标
            int maxLength=newFlag+1+nums[flag+currentLength];
            currentLength--;
            while(currentLength>0) {  //循环遍历找下一个最大路径
                int tempLength=flag+1+currentLength+nums[flag+currentLength];
                if(tempLength>maxLength) {     //如果找下一个下标的值大就记录
                    maxLength=tempLength;
                    newFlag=flag+currentLength;
                }
                currentLength--;
            }
            flag=newFlag;
        }
        return false;
    }

    public int jump(int[] nums) {
        int n = nums.length;
        int res=0;
        if(n==1) return res;
        int flag=0;  //flag是下标
        while(flag<n) {
            int currentLength=nums[flag];  //记录当前最大值
//            if(currentLength==0) break;
            if(flag+1+currentLength>=n) {
                return res+1;
            }
            int newFlag=flag+currentLength;  //找新最大路径的下标
            int maxLength=newFlag+1+nums[flag+currentLength];
            currentLength--;
            while(currentLength>0) {  //循环遍历找下一个最大路径
                int tempLength=flag+1+currentLength+nums[flag+currentLength];
                if(tempLength>maxLength) {     //如果找下一个下标的值大就记录
                    maxLength=tempLength;
                    newFlag=flag+currentLength;
                }
                currentLength--;
            }
            flag=newFlag;
            res++;
        }
        return -1;
    }
}
